package tree;

import com.sun.source.tree.Tree;

public class BinarySearchTree {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root;

    //搜索
    public TreeNode search(int key) {
        TreeNode cur = root;
        while(cur != null) {
            if(cur.val == key) {
                return cur;
            } else if(cur.val > key) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        return null;
    }

    //插入
    public void insert(int key) {
        TreeNode node = new TreeNode(key);
        if(root == null) {
            root = node;
            return;
        }

        TreeNode cur = root;
        TreeNode prev = null;

        while(cur != null) {
            if(cur.val == key) {
                return;
            } else if(cur.val > key) {
                prev = cur;
                cur = cur.left;
            } else {
                prev = cur;
                cur = cur.right;
            }
        }

        if(key > prev.val) {
            prev.right = node;
        } else {
            prev.left = node;
        }
    }

    public void remove(int key) {
        TreeNode prev = null;
        TreeNode cur = root;

        while(cur != null) {
            if(cur.val > key) {
                prev= cur;
                cur = cur.left;
            } else if(cur.val < key) {
                prev= cur;
                cur = cur.right;
            } else {
                removeNode(prev,cur);
                return;
            }
        }
    }

    private void removeNode(TreeNode parent,TreeNode del) {
        if(del.left == null) {
            if(del == root) {
                root = del.right;
            } else if(parent.left == del) {
                parent.left = del.right;
            } else {
                parent.right = del.right;
            }
        } else if(del.right == null) {
            if(del == root) {
                root = del.left;
            } else if(parent.left == del) {
                parent.left = del.left;
            } else {
                parent.right = del.left;
            }
        } else {
            TreeNode prev = del;
            TreeNode cur = del.right;
            while(cur.left != null) {
                prev = cur;
                cur = cur.left;
            }

            del.val = cur.val;
            if(prev.right == cur) {
                prev.right = cur.right;
            } else {
                prev.left = cur.right;
            }
        }
    }

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(10);
        bst.insert(5);
        bst.insert(15);
        bst.insert(9);
        bst.insert(3);
        bst.insert(18);

        BinarySearchTree.TreeNode ret = bst.search(15);
        System.out.println(ret.val);

        bst.remove(10);
    }
}
